Article 939

Title of the article

APPROXIMATION ALGORITHMS AND PREUDOMETRIC VARIANT OF A TRAVELLING SALESMAN PROBLEM

Authors

Borisova Elena Sergeevna, Post graduate student, Togliatti State University, e-lena-borisova@mail.ru
Melnikov Boris Felixovich, Doctor of physico-mathematical sciences, professor, sub-department of applied mathematics and applied computer science, Togliatti State University, B.Melnikov@tltsu.ru

Index UDK

004.021:519.8:519.724.6

Abstract

An Article contains classical approach to approximation algorithms, there are given examples illustrating the basic definition of these algorithms. There are contained polynomial-time approximation scheme and fully polynomial-time approximation scheme. There is cited an example psevdometric traveling salesperson problem. Efficient algorithms giving optimal solution this problem haven’t yet developed.

Key words

approximation algorithms, relative error, approximation ratio, approximation scheme, psevdometric traveling salesperson problem.

Download PDF

 

Дата создания: 11.07.2014 10:01
Дата обновления: 11.07.2014 11:26